3.1.1 Using k-means

1. The k-means algorithm randomly selects k data points as initial means
2. k clusters are formed by assigning each data point to its closest cluster mean using the Euclidean distance
3. Virtual means for each cluster are calculated by using all datapoints contained in a cluster

The second and third steps are iterated until a predefined number of iterations is reached or the clusters converge. The runtime for the algorithm is O(n).

3.1.2 Using k-medoids

1. The k-medoids algorithm randomly selects k data points as initial means out of the n data points as the medoids.
2. k clusters are formed by assigning each data point to its closest medoid by using any common distance metric methods.
3. Virtual means for each cluster are calculated by using all datapoints contained in a cluster

The second and third steps are iterated until a predefined number of iterations is reached or the clusters converge. The runtime for the algorithm is O(k * (n-k)^2) .

3.1.3 Hierarchical Vector Quantization

The algorithm divides the dataset recursively into cells using \(k-means\) or \(k-medoids\) algorithm. The maximum number of subsets are decided by setting \(n_cells\) to, say five, in order to divide the dataset into maximum of five subsets. These five subsets are further divided into five subsets(or less), resulting in a total of twenty five (5*5) subsets. The recursion terminates when the cells either contain less than three data point or a stop criterion is reached. In this case, the stop criterion is set to when the cell error exceeds the quantization threshold.

The steps for this method are as follows :

1. Select k(number of cells), depth and quantization error threshold
2. Perform quantization (using \(k-means\) or \(k-medoids\)) on the input dataset
3. Calculate quantization error for each of the k cells
4. Compare the quantization error for each cell to quantization error threshold
5. Repeat steps 2 to 4 for each of the k cells whose quantization error is above threshold until stop criterion is reached.

The stop criterion is when the quantization error of a cell satisfies one of the below conditions

• reaches below quantization error threshold
• there are less than three data points in the cell
• the user specified depth has been attained

The quantization error for a cell is defined as follows :

\[QE = \max_i(||A-F_i||_{p})\]

where

• \(A\) is the centroid of the cell
• \(F_i\) represents a data point in the cell
• \(m\) is the number of points in the cell
• \(p\) is the \(p\)-norm metric. Here \(p\) = 1 represents L1 Norm and \(p\) = 2 represents L2 Norm.

3.1.4 Quantization Error

Let us try to understand quantization error with an example.

Figure 2: The Voronoi tessellation for level 1 shown for the 5 cells with the points overlayed

An example of a 2 dimensional VQ is shown above.

In the above image, we can see 5 cells with each cell containing a certain number of points. The centroid for each cell is shown in blue. These centroids are also known as codewords since they represent all the points in that cell. The set of all codewords is called a codebook.

Now we want to calculate quantization error for each cell. For the sake of simplicity, let’s consider only one cell having centroid A and m data points \(F_i\) for calculating quantization error.

For each point, we calculate the distance between the point and the centroid.

\[ d = ||A - F_i||_{p} \]

In the above equation, p = 1 means L1_Norm distance whereas p = 2 means L2_Norm distance. In the package, the L1_Norm distance is chosen by default. The user can pass either L1_Norm, L2_Norm or a custom function to calculate the distance between two points in n dimensions.

\[QE = \max_i(||A-F_i||_{p})\]

Now, we take the maximum calculated distance of all m points. This gives us the furthest distance of a point in the cell from the centroid, which we refer to as Quantization Error. If the Quantization Error is higher than the given threshold, the centroid/ codevector is not a good representation for the points in the cell. Now we can perform further Vector Quantization on these points and repeat the above steps.

Please note that the user can select mean, max or any custom function to calculate the Quantization Error. The custom function takes a vector of m value (where each value is a distance between point in n dimensions and centroids) and returns a single value which is the Quantization Error for the cell.

If we select mean as the error metric, the above Quantization Error equation will look like this :

\[QE = \frac{1}{m}\sum_{i=1}^m||A-F_i||_{p}\]

4.2.1 Example Usage 1

In this section, we will use the Prices of Personal Computers dataset. This dataset contains 6259 observations and 10 features. The dataset observes the price from 1993 to 1995 of 486 personal computers in the US. The variables are price, speed, ram, screen, cd, etc. The dataset can be downloaded from here.

In this example, we will compress this dataset by using hierarchical VQ via k-means and visualize the Voronoi Tessellation plots using Sammons projection. Later on, we will overlay price and speed variables as a heatmap to generate further insights.

Here, we load the data and store into a variable computers.

set.seed(240)
# Load data from csv files
computers <- read.csv("https://raw.githubusercontent.com/Mu-Sigma/muHVT/dev/vignettes/sample_dataset/Computers.csv")

Let’s have a look at some of the data

# Quick peek
Table(head(computers))

Now let us check the structure of the data

str(computers)
#> 'data.frame':    6259 obs. of  11 variables:
#>  $ X      : int  1 2 3 4 5 6 7 8 9 10 ...
#>  $ price  : int  1499 1795 1595 1849 3295 3695 1720 1995 2225 2575 ...
#>  $ speed  : int  25 33 25 25 33 66 25 50 50 50 ...
#>  $ hd     : int  80 85 170 170 340 340 170 85 210 210 ...
#>  $ ram    : int  4 2 4 8 16 16 4 2 8 4 ...
#>  $ screen : int  14 14 15 14 14 14 14 14 14 15 ...
#>  $ cd     : chr  "no" "no" "no" "no" ...
#>  $ multi  : chr  "no" "no" "no" "no" ...
#>  $ premium: chr  "yes" "yes" "yes" "no" ...
#>  $ ads    : int  94 94 94 94 94 94 94 94 94 94 ...
#>  $ trend  : int  1 1 1 1 1 1 1 1 1 1 ...

Let’s get a summary of the data

summary(computers)
#>        X            price          speed              hd        
#>  Min.   :   1   Min.   : 949   Min.   : 25.00   Min.   :  80.0  
#>  1st Qu.:1566   1st Qu.:1794   1st Qu.: 33.00   1st Qu.: 214.0  
#>  Median :3130   Median :2144   Median : 50.00   Median : 340.0  
#>  Mean   :3130   Mean   :2220   Mean   : 52.01   Mean   : 416.6  
#>  3rd Qu.:4694   3rd Qu.:2595   3rd Qu.: 66.00   3rd Qu.: 528.0  
#>  Max.   :6259   Max.   :5399   Max.   :100.00   Max.   :2100.0  
#>       ram             screen           cd               multi          
#>  Min.   : 2.000   Min.   :14.00   Length:6259        Length:6259       
#>  1st Qu.: 4.000   1st Qu.:14.00   Class :character   Class :character  
#>  Median : 8.000   Median :14.00   Mode  :character   Mode  :character  
#>  Mean   : 8.287   Mean   :14.61                                        
#>  3rd Qu.: 8.000   3rd Qu.:15.00                                        
#>  Max.   :32.000   Max.   :17.00                                        
#>    premium               ads            trend      
#>  Length:6259        Min.   : 39.0   Min.   : 1.00  
#>  Class :character   1st Qu.:162.5   1st Qu.:10.00  
#>  Mode  :character   Median :246.0   Median :16.00  
#>                     Mean   :221.3   Mean   :15.93  
#>                     3rd Qu.:275.0   3rd Qu.:21.50  
#>                     Max.   :339.0   Max.   :35.00

Let us first split the data into train and test. We will use 80% of the data as train and remaining as test.

noOfPoints <- dim(computers)[1]
trainLength <- as.integer(noOfPoints * 0.8)

trainComputers <- computers[1:trainLength,]
testComputers <- computers[(trainLength+1):noOfPoints,]

K-means is not suitable for factor variables as the sample space for factor variables is discrete. A Euclidean distance function on such a space isn’t really meaningful. Hence, we will delete the factor variables in our dataset.

Here we keep the original trainComputers and testComputers as we will use the price variable from this dataset to overlay as heatmap and generate some insights.

trainComputers <-
  trainComputers %>% dplyr::select(-c(X, cd, multi, premium, trend))
testComputers <-
  testComputers %>% dplyr::select(-c(X, cd, multi, premium, trend))

Let us try to understand the HVT function first.

HVT(
  dataset,
  n_cells,
  depth,
  quant.err,
  projection.scale,
  normalize = T,
  distance_metric = c("L1_Norm", "L2_Norm"),
  error_metric = c("mean", "max"),
  quant_method = c("kmeans", "kmedoids"),
  diagnose = TRUE,
  hvt_validation = FALSE,
  train_validation_split_ratio = 0.8
)

Each of the parameters have been explained below :

• dataset - A dataframe with numeric columns

• n_cells - An integer indicating the number of cells per hierarchy (level)

• depth - An integer indicating the number of levels. (1 = No hierarchy, 2 = 2 levels, etc …)

• quant.error - A number indicating the quantization error threshold. A cell will only breakdown into further cells if the quantization error of the cell is above the defined quantization error threshold

• distance_metric - The distance metric can be L1_Norm or L2_Norm. L1_Norm is selected by default. The distance metric is used to calculate the distance between an n dimensional point and centroid. The user can also pass a custom function to calculate this distance

• error_metric - The error metric can be mean or max. max is selected by default. max will return the max of m values and mean will take mean of m values where each value is a distance between a point and centroid of the cell. Moreover, the user can also pass a custom function to calculate the error metric

• quant_method - The quantization method can be kmeans or kmedoids. kmeans is selected by default

• normalize - A logical value indicating whether the columns in your dataset need to be normalized. Default value is TRUE. The algorithm supports Z-score normalization

• diagnose - A logical value indicating whether user wants to perform diagnostics on the model. Default value is TRUE.

• hvt_validation - A logical value indicating whether user wants to holdout a validation set and find mean absolute deviation of the validation points from the centroid. Default value is FALSE.

• train_validation_split_ratio - A numeric value indicating train validation split ratio. This argument is only used when hvt_validation has been set to TRUE. Default value for the argument is 0.8

First we will perform hierarchical Vector Quantization at level 1 by setting the parameter depth to 1 and the number of cells to 15. Here, level 1 signifies no hierarchy.

set.seed(240)
hvt.results <- list()
hvt.results <- muHVT::HVT(trainComputers,
                          n_cells = 15,
                          depth = 1,
                          quant.err = 0.2,
                          projection.scale = 10,
                          normalize = T,
                          distance_metric = "L1_Norm",
                          error_metric = "mean",
                          quant_method = "kmeans")

Now let’s try to understand plotHVT function. The parameters have been explained in detail below

plotHVT(hvt.results, line.width, color.vec, pch1 = 21, centroid.size = 3, title = NULL, maxDepth = 1)

• hvt.results - A list containing the output of the HVT function which has the details of the tessellations to be plotted

• line.width - A vector indicating the line widths of the tessellation boundaries for each level

• color.vec - A vector indicating the colors of the tessellations boundaries at each level

• pch1 - Symbol type of the centroids of the tessellations (parent levels). Refer points (default = 21)

• centroid.size - Size of centroids of first level tessellations (default = 3)

• title - Set a title for the plot (default = NULL)

Let’s plot the Voronoi tessellation

# Voronoi tessellation plot for level one
muHVT::plotHVT(hvt.results,
        line.width = c(0.6), 
        color.vec = c("#141B41"),
        centroid.size = 1.5,
        maxDepth = 1)

Figure 3: The Voronoi Tessellation for level 1 shown for the 15 cells in the dataset ’computers’

As per the manual, hvt.results[[3]] gives us detailed information about the hierarchical vector quantized data.

hvt.results[[3]][['summary']] gives a nice tabular data containing no of points, Quantization Error and the codebook.

Now let us understand what each column in the above table means:

• Segment.Level - Level of the cell. In this case, we have performed Vector Quantization for depth 1. Hence Segment Level is 1

• Segment.Parent - Parent segment of the cell

• Segment.Child (Cell.Number) - The children of a particular cell. In this case, it is the total number of cells at which we achieved the defined compression percentage

• n - No of points in each cell

• Cell.ID - Cell_ID’s are generated for the multivariate data using 1-D Sammon’s Projection algorithm

• Quant.Error - Quantization Error for each cell

All the columns after this will contain centroids for each cell. They can also be called a codebook, which represents a collection of all centroids or codewords.

summaryTable(hvt.results[[3]][['summary']])

Let’s have a look at Quant.Error variable in the above table. It seems that none of the cells have hit the quantization threshold error.

Now let’s check the compression summary. The table below shows no of cells, no of cells having quantization error below threshold and percentage of cells having quantization error below threshold for each level.

compressionSummaryTable(hvt.results[[3]]$compression_summary)

As it can be seen in the table above, percentage of cells in level 1 having Quantization Error below threshold is 0%. Hence, we can go one level deeper and try to compress it further.

We will now overlay the Quant.Error variable as heatmap over the Voronoi Tessellation plot to visualize the quantization error better.

Let’s have look at the function hvtHmap which we will use to overlay a variable as heatmap.

hvtHmap(hvt.results, dataset, child.level, hmap.cols, color.vec ,line.width, palette.color = 6)

• hvt.results - A list of hvt.results obtained from the HVT function

• dataset - A dataframe containing the variables to overlay as a heatmap. The user can pass an external dataset or the dataset that was used to perform hierarchical vector quantization. The dataset should have the same number of points as the dataset used to perform hierarchical Vector Quantization in the HVT function

• child.level - A number indicating the level for which the heat map is to be plotted

• hmap.cols - The column number of column name from the dataset indicating the variables for which the heat map is to be plotted. To plot the quantization error as heatmap, pass 'quant_error'. Similarly to plot the no of points in each cell as heatmap, pass 'no_of_points' as a parameter

• color.vec - A color vector such that length(color.vec) = child.level (default = NULL)

• line.width - A line width vector such that length(line.width) = child.level (default = NULL)

• palette.color - A number indicating the heat map color palette. 1 - rainbow, 2 - heat.colors, 3 - terrain.colors, 4 - topo.colors, 5 - cm.colors, 6 - BlCyGrYlRd (Blue,Cyan,Green,Yellow,Red) color (default = 6)

• show.points - A boolean indicating whether the centroids should be plotted on the tessellations (default = FALSE)

Now let’s plot the quantization error for each cell at level one as a heatmap.

muHVT::hvtHmap(
  hvt.results,
  trainComputers,
  child.level = 1,
  hmap.cols = "Quant.Error",
  line.width = c(0.2),
  color.vec = c("#141B41"),
  palette.color = 6,
  centroid.size = 1.5,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 15
)

Figure 4: The Voronoi Tessellation with the heat map overlaid for variable ’quant_error’ in the ’computers’ dataset

Now let’s go one level deeper and perform hierarchical vector quantization.

set.seed(240)
hvt.results2 <- list()
# depth=2 is used for level2 in the hierarchy
hvt.results2 <- muHVT::HVT(
  trainComputers,
  n_cells = 15,
  depth = 2,
  quant.err = 0.2,
  projection.scale = 10,
  normalize = T,
  distance_metric = "L1_Norm",
  error_metric = "mean",
  quant_method = "kmeans"
)

Let’s plot the Voronoi tessellation for both the levels.

# Voronoi tessellation plot for level two
muHVT::plotHVT(
  hvt.results2,
  line.width = c(0.6, 0.4),
  color.vec = c("#141B41", "#0582CA"),
  centroid.size = 1.5,
  maxDepth = 2
)

Figure 5: The Voronoi Tessellation for level 2 shown for the 225 cells in the dataset ’computers’

In the table below, Segment Level signifies the depth.

Level 1 has 15 cells

Level 2 has 225 cells .i.e. each cell in level 1 is divided into 15 cells each

Let’s analyze the summary table again for Quant.Error and see if any of the cells in the 2nd level have Quantization Error below the Quantization Error threshold. In the table below, the values for Quant.Error of the cells which have hit the Quantization Error threshold are shown in red. Here we are showing just top 50 rows for the sake of brevity.

summaryTable(hvt.results2[[3]][['summary']],limit = 50)

The users can look at the compression summary to get a quick summary on the compression as it becomes quite cumbersome to look at the summary table above as we go deeper.

compressionSummaryTable(hvt.results2[[3]]$compression_summary)

As it can be seen in the table above, only 85% cells in the 2nd level have Quantization Error below threshold. Therefore, we can go another level deeper and try to compress the data further.

We will look at the heatmap for Quantization Error for level 2.

muHVT::hvtHmap(
  hvt.results2,
  trainComputers,
  child.level = 2,
  hmap.cols = "Quant.Error",
  line.width = c(0.6, 0.4),
  color.vec = c("#141B41", "#0582CA"),
  palette.color = 6,
  centroid.size = 2,
  show.points = T,
  quant.error.hmap = 0.2,
  n_cells.hmap = 15
)

Figure 6: The Voronoi Tessellation with the heat map overlaid for variable ’quant_error’ in the ’computers’ dataset

As the Quantization Error criteria is not met, let’s perform hierarchical Vector Quantization at level 3.

set.seed(240)
hvt.results3 <- list()
# depth=3 is used for level3 in the hierarchy
hvt.results3 <- muHVT::HVT(
  trainComputers,
  n_cells = 15,
  depth = 3,
  quant.err = 0.2,
  projection.scale = 10,
  normalize = T,
  distance_metric = "L1_Norm",
  error_metric = "mean",
  quant_method = "kmeans"
)

Let’s plot the Voronoi Tessellation for all 3 levels.

# Voronoi tessellation plot for level three
muHVT::plotHVT(
  hvt.results3,
  line.width = c(0.6, 0.4, 0.2),
  color.vec = c("#141B41", "#0582CA", "#8BA0B4"),
  centroid.size = 1.5,
  maxDepth = 3
)

Figure 7: The Voronoi Tessellation for level 3 shown for the 1905 cells in the dataset ’computers’

Each of the 225 cells whose quantization is above the defined threshold in level 2 will break down into 15 cells each in level 3. Hence, as it can be seen below, level 3 has 3375 rows. So it will have 3615 rows in total. We will only show first 500 rows here.

summaryTable(hvt.results3[[3]][['summary']],scroll = T,limit = 500)